﻿#include "stdafx.h"
#include "MergeTwoSortedLists.h"

using namespace std;

namespace algorithm {
ListNode* CMergeTwoSortedLists::Merge(ListNode* list1, ListNode* list2)
{
    // 生成空头节点，避免需要对list1与list2为空特殊判断
    ListNode head1(0, list1);
    ListNode head2(0, list2);
    // 指向链表，用于遍历
    ListNode* head1Node = &head1;
    ListNode* head2Node = &head2;
    // 指向当前需要操作的链表指针，因为每次操作逻辑相同，都是将某一个链表的数据增加到结果链表，然后遍历下一个节点
    ListNode** opNode = nullptr;
    // 结果链表空头节点，避免添加第一个链表节点需要特殊处理
    ListNode result;
    // 指向结果链表，执行下一个待存储节点
    ListNode* node = &result;
    while (1) {
        if (head1Node->next && head2Node->next) {
            opNode = (head1Node->next->val <= head2Node->next->val) ? &head1Node : &head2Node;
        }
        else if (head1Node->next) {
            opNode = &head1Node;
        }
        else if (head2Node->next) {
            opNode = &head2Node;
        }
        else {
            break;
        }

        //printf("val=>%d\n", (*opNode)->next->val);
        node->next = new ListNode((*opNode)->next->val);
        node = node->next;
        (*opNode) = (*opNode)->next;
    }

    return result.next;
}
}
